// 73.矩阵置零

package Leetcode;

import java.util.ArrayList;
import java.util.List;

class solution_073 {
    public void setZeroes(int[][] matrix) {
        List<Integer> row = new ArrayList<>();
        List<Integer> line = new ArrayList<>();
        for (int i = 0; i < matrix.length; i++)
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    row.add(i);
                    line.add(j);
                }
            }
        for (int i : row)
            for (int j = 0; j < matrix[0].length; j++)
                matrix[i][j] = 0;
        for (int j : line)
            for (int i = 0; i < matrix.length; i++)
                matrix[i][j] = 0;

    }
}

public class Solution073 {
    public void setZeroes(int[][] matrix) {
        int m = matrix.length;
        int n = matrix[0].length;
        boolean flag = false; // 用于表示原矩阵中第一列是否有0
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == 0)
                flag = true;
            // 如果除第一列元素之外有元素为0，则把其对应第一行和第一列元素变成0用于标记
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                } // if
            } // for-j
        } // for-i
          // 行遍历从后往前，如果改元素的第一行或第一列元素为0则表示该元素为0
        for (int i = m - 1; i >= 0; i--) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0)
                    matrix[i][j] = 0;
            }
            // 判断第一列是否置0
            if (flag) {
                matrix[i][0] = 0;
            }//if
        }//for-i
    }
}
